The problem can be found at the following link: Question Link
- I iterate through the given string and count the frequency of each character using an unordered_map.
- I find the minimum and maximum frequencies among all characters.
- I check if the difference between the maximum and minimum frequencies is more than 1. If it is, return 0 (false).
- I count the number of characters having the minimum frequency.
- I check if the difference between the total number of unique characters and the number of characters with the minimum frequency is at most 1. If it is, return 1 (true), indicating that frequencies can be made equal.
- Time Complexity : O
(N)
, where N is the length of the input string. - Auxiliary Space Complexity : At most, 26 unique characters can be used, resulting in a time complexity of
O(26)
class Solution {
public:
bool sameFreq(string s)
{
unordered_map<char,int> cnt;
for(auto i: s)
cnt[i]++;
int nin, nax;
nin = nax = cnt[s[0]];
for(auto i: cnt){
nin = min(nin, i.second);
nax = max(nax, i.second);
if(nax - nin > 1)
return 0;
}
int cnin = 0;
for(auto i: cnt)
if(i.second == nin)
++cnin;
return cnt.size() - cnin <= 1;
}
};
For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star
to the getlost01/gfg-potd repository.